1. Field of the Invention
This invention relates to cryptographic systems, and more specifically to public-key digital signature systems providing unlinkability.
2. Description of Prior Art
Blind signatures are known in the art, as described in European Patent Publication No. 0139313, dated 2/5/85, claiming priority on U.S. Ser. No. 524896, titled "Blind signature systems," and European Patent Publication No. 0218305, dated 4/15/87, claiming priority on U.S. Ser. No. 784999, titled "Unanticipated blind signature systems," both by the present applicant.
These signatures can be used rather directly to construct a payment system (as described, for instance, in the applicant's "Security without identification: Transaction systems to make Big-Brother obsolete," Communications of the ACM, Oct. 1985, pp. 1030-1044.) In such systems, a bank might charge, say, one dollar to make a blind signature. People can buy such signatures from the bank (the blinding lets them keep the bank from learning which ones they bought) and then spend them at, say, a shop. The shop could check with the bank in an on-line transaction to verify upon receiving a particular signature that it has not already been spent elsewhere. If shops do not perform such checking, then someone could spend the same number in more than one shop, and the blind signatures would protect them from ever being traced. But on-line checking may be costly or even infeasible in many applications.
Another use of blind signatures is in credential mechanisms. These were also introduced in the article cited above, and have since been further detailed in "A secure and privacy-protecting protocol for transmitting personal information between organizations," that appeared in Proceedings of Crypto 86, A. M. Odlyzko Ed., Springer-Verlag, 1987, by the present applicant and J. -H. Evertse. When "digital pseudonyms" are established for showing or receiving credentials in such mechanisms, it may be necessary to perform an on-line transaction to ensure that the same pseudonym has not already been used before.
In all these systems, there are essentially three parties: (1) the signature issuing party; (2) the plurality of parties to whom signatures are issued by the first party; and (3) the pluarlity of parties to whom the signatures are shown by the second parties. One aspect that could be improved-without reducing unlinkability for "honest" second parties-is that the third parties must check with one another or some clearing center before accepting a signature, otherwise they will have no recourse if it turns out that the same signature has already been shown to more than a single third party.